class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []   
        def backtrace(left, right, cur_ans):
            if left == 0 and right == 0:
                ans.append(cur_ans)
                return
            
            #剩余的左括号多于右括号
            if left > right:
                return
            
            if left > 0:
                cur_ans += "("
                backtrace(left - 1, right, cur_ans)
                cur_ans = cur_ans[:-1]
            
            if right > 0:
                cur_ans += ")"
                backtrace(left, right - 1, cur_ans)
                cur_ans = cur_ans[:-1]
        backtrace(n, n, "")
        return ans
